package org.lex.utils.collections;

import java.util.Arrays;
import java.util.EmptyStackException;
import java.util.Iterator;

/**
 * java.util.Stackֱ����Vector�̳ж�������Ȼʵ�ּ򵥣�����2����Ҫ���⣺
 * 1��Vector�������߳�ͬ���ģ�ʹ��java.util.StackҲ��ͬ���ġ�����ʱ������Ҫ�������ԡ�
 * 2���̳
 * ���Vectorʹ��java.util.Stack��������������޸ķ���(����get(int),remove(int))��
 * ʹ��ʱ������Ի�,���ҿ�����ʹ���д���Ǳ�ڵ�Σ��.
 */
public class ArrayStack<T> implements Stack<T> {
	private static final int DEFAULT_INITIAL_CAPACITY = 8;
	/*
	 * The array buffer into which the elements of the ArrayStack are stored.
	 * The capacity of the ArrayStack is the length of this array buffer.
	 */
	private transient Object[] data = null;
	/*
	 * The size of the ArrayStack (the number of elements it contains).
	 */
	private int size = 0;

	/**
	 * Constructs an empty stack with the specified initial capacity.
	 * 
	 * @param initialCapacity
	 *            the initial capacity of the list
	 * @exception IllegalArgumentException
	 *                if the specified initial capacity is negative
	 */
	public ArrayStack(int initialCapacity) {
		super();
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
		this.data = new Object[initialCapacity];
	}

	/**
	 * Constructs an empty stack with default initial capacity.
	 */
	public ArrayStack() {
		this(DEFAULT_INITIAL_CAPACITY);
	}

	// ====================
	public boolean isEmpty() {
		return 0 == size;
	}

	@SuppressWarnings("unchecked")
	public T peek() {
		if (0 == size)
			throw new EmptyStackException();
		return (T) this.data[size - 1];
	}

	@SuppressWarnings("unchecked")
	public T pop() {
		if (0 == size)
			throw new EmptyStackException();
		size -= 1;
		T value = (T) this.data[size];
		this.data[size] = null;
		return value;
	}

	public void push(T e) {
		ensureCapacity(size + 1);
		this.data[size++] = e;
	}

	public void clear() {
		if (0 == size)
			return;
		Arrays.fill(this.data, 0, size - 1, null);
		size = 0;
	}

	public int size() {
		return size;
	}

	@SuppressWarnings("unchecked")
	public Iterator<T> iterator() {
		return (Iterator<T>) Collections.toIterator(this.data);
	}

	/**
	 * Increases the capacity of this <tt>ArrayStack</tt> instance, if
	 * necessary, to ensure that it can hold at least the number of elements
	 * specified by the minimum capacity argument.
	 * 
	 * @param minCapacity
	 *            the desired minimum capacity
	 */
	protected void ensureCapacity(int minCapacity) {
		if (data.length < minCapacity) {
			int newLength = data.length * 2;
			if (newLength <= 0)
				newLength = Integer.MAX_VALUE;
			newLength = Math.max(newLength, minCapacity);
			Object[] newData = Arrays.copyOf(data, newLength);
			// do we need to to this?
			Arrays.fill(data, null);
			data = newData;
		}
	}

	public String toString() {
		return this.toString(", ");
	}

	public String toString(String sep) {
		StringBuilder buffer = new StringBuilder();
		buffer.append('[');
		for (int i = 0; i < size; i++) {
			buffer.append(String.valueOf(this.data[i]));
			buffer.append(sep);
		}
		if (buffer.length() > sep.length())
			buffer.setLength(buffer.length() - sep.length());
		buffer.append(']');
		return buffer.toString();
	}
}
